;2008-05-20
;Av Benjamin Ingberg och Patrik Johansson
;
;Sorterar, snabbt med en quicksort algoritm, borde ha en typ O(n log n) i komplexitet

(define (singleton? list)
  (and (list? list)
       (not (null? list))
       (null? (cdr list))))

(define (quicksort lon get-value)
  (cond ((null? lon) '())
        ((singleton? lon) lon)
        (else (let ((parts (partition (car lon) (cdr lon) get-value)))
                (append (quicksort (car parts) get-value)
                        (list (car lon))
                        (quicksort (cdr parts) get-value))))))

(define (partition pivot elements get-value)
  (partition-it pivot elements '() '() get-value))

(define (partition-it pivot elements low high get-value)
  (cond ((null? elements) (cons low high))
        ((<= (get-value (car elements))
             (get-value pivot)) (partition-it pivot
                                              (cdr elements)
                                              (cons (car elements) low)
                                              high
                                              get-value))
        (else (partition-it pivot
                            (cdr elements)
                            low
                            (cons (car elements) high)
                            get-value))))
